package main

import "fmt"

func main() {
	stones := []int{0, 1, 3, 5, 6, 8, 12, 17}
	fmt.Println(canCross(stones))
}

/**
 * @Description:
 dp[i][k] i表示从跳到下标为i的石头上，k表示前一块石头跳了几步
 dp[0][0]=true,第一个石头上肯定为true
 dp[i][k]=dp[j][k-1]||dp[j][k]||dp[j][k+1],i上的石头可能从j跳了k-1步，k步，k+1步

最好的状态就是第一次跳1单位距离，第二次跳2单位距离...第n次跳n单位距离，所以stone[i]-stone[j]>j+1

【参考了题解】https://leetcode-cn.com/problems/frog-jump/solution/403-qing-wa-guo-he-li-jie-li-jie-dong-ta-oyt9/
 * @param stones
 * @return bool
*/
func canCross(stones []int) bool {
	n := len(stones)
	dp := make([][]bool, n)
	//todo: 坑点，二维数组要记得初始化
	for i := range dp {
		dp[i] = make([]bool, n)
	}
	dp[0][0] = true
	for i := 1; i < n; i++ {
		for j := i - 1; j >= 0; j-- {
			k := stones[i] - stones[j]
			if k > j+1 {
				break
			}
			dp[i][k] = dp[j][k-1] || dp[j][k] || dp[j][k+1]
			if i == n-1 && dp[i][k] {
				return true
			}
		}
	}
	return false
}
